package top.minuy.structure.queue;

/**
 * 使用size
 * 不浪费一个空间?
 *
 * @author Minuy
 * @time 20:14
 * @date 2021/8/22
 */
public class LoopQueueWork_1<E> implements Queue<E> {

    // 数据数组
    private E[] data;
    // 头坐标和尾坐标
    private int front, tail;
    // 队列大小（后期可替换）
    private int size;

    /**
     * 创建一个循环队列对象
     *
     * @param capacity 队列的容量
     */
    public LoopQueueWork_1(int capacity) {
        this.data = (E[]) new Object[capacity];
        this.size = 0;
        this.front = 0;
        this.tail = 0;
    }

    /**
     * 使用默认容量创建队列
     */
    public LoopQueueWork_1() {
        this(10);
    }

    /**
     * 获取队列的元素个数
     *
     * @return 元素个数
     */
    @Override
    public int getSize() {
        return size;
    }

    /**
     * 获取当前队列的容量
     *
     * @return 队列容量
     */
    public int getCapacity() {
        // 故意浪费了一个容量
        return data.length;
    }

    /**
     * 判断队列是否为空
     *
     * @return 是否为空
     */
    @Override
    public boolean isEmpty() {
        // 我们定义的判空
        // 不浪费空间满队也是front == tail，附加size判断
        // 考虑到size==0可以更快否决，放前面
        return this.size == 0 && this.front == this.tail;
    }

    /**
     * 入队，将元素添加到队尾
     *
     * @param e 放入的元素
     */
    @Override
    public void enqueue(E e) {
        // 判断满队，需要size帮助
        if (size == data.length && this.tail == this.front) {
            // 队列满了，需要扩容
            // 这里不使用data.length而使用getCapacity是因为浪费了一个空间
            this.resize(getCapacity() * 2);
        }

        this.data[this.tail] = e;
        this.tail = (this.tail + 1) % this.data.length;
        this.size++;
    }


    /**
     * 出队，将元素从队首拿出
     *
     * @return 拿出的元素
     */
    @Override
    public E dequeue() {
        if (this.isEmpty()) {
            throw new IllegalArgumentException("Dequeue failed, Loop Queue is Empty.");
        }
        E res = this.data[this.front];

        // 提前释放内存
        this.data[this.front] = null;

        this.front = (this.front + 1) % this.data.length;
        this.size--;

        // 这里因为容量跟data.length是不一样的，以容量为准
        if (this.size <= this.getCapacity() / 4 && this.getCapacity() / 2 != 0) {
            this.resize(this.getCapacity() / 2);
        }

        return res;
    }

    /**
     * 获取队首的元素
     *
     * @return 队首的元素
     */
    @Override
    public E getFront() {
        if (this.isEmpty()) {
            throw new IllegalArgumentException("GetFront failed. Loop Queue is Empty.");
        }
        return this.data[this.front];
    }

    private void resize(int newCapacity) {
        E[] newData = (E[]) new Object[newCapacity];

        // 把原来旧数组的值重新整理，这样比较方便，即把队首front指0
        // 但是这样新数组的下标和旧数组的就需要一个映射关系，而不是直接相等
        // TODO 想想直接复制会有什么问题
        // 直接复制，若尾在头前面，则会导致后面多出的空间无法使用
        for (int i = 0; i < this.size; i++) {
            // 顺序对应着头索引对i的循环偏移
            newData[i] = this.data[(this.front + i) % this.data.length];
        }

        // 维护一下
        this.data = newData;
        this.front = 0;
        // 整理后就是尾的长度
        this.tail = this.size;
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("Loop Queue : size = %d, capacity = %d\n", this.getSize(), this.getCapacity()));
        res.append("front [");
        // 换一种循环方式，跟resize不一样
        /*
         * 这边跟之前的不一样，
         * 因为没有空的空间，
         * 所以之前的推出循环条件不能继续用，
         * 得换
         */
        /*for (int i = this.front; i != this.tail || (size == this.getCapacity() && i == this.tail); i = (i + 1) % this.data.length) {
            top.minuy.res.append(this.data[i].toString());
            // 判断最后一个，即tail-1
            if ((i + 1) % data.length != this.tail) { // 这边考虑到越界的情况，负数取余是可以的
                top.minuy.res.append(", ");
            }
            // System.out.println(String.format("tail = %d , data.length = %d , (this.tail - 1) 取余 data.length = %d , i = %d",tail,data.length,(this.tail - 1) % data.length,i));
        }
         */

        for (int i = 0; i < this.size; i++) {
            // 顺序对应着头索引对i的循环偏移
            res.append(this.data[(this.front + i) % this.data.length].toString());
            if (i != this.size-1) {
                res.append(", ");
            }
        }

        res.append("] tail");

        return res.toString();
    }
}
